#include "Tree.h"


class Solution {
public:
    void dfs(TreeNode* root, int k, vector<vector<int>>& ans)
    {
        if (root == NULL) return;
        if (k == ans.size()) ans.push_back(vector<int>());
        ans[k].push_back(root->val);
        dfs(root->left, k + 1, ans);
        dfs(root->right, k + 1, ans);
    }
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        dfs(root, 0, ans);
        for (int i = 0; i < ans.size(); i++)
        {
            if (i % 2 == 1)reverse(ans[i].begin(), ans[i].end());
        }
        return ans;
    }
};